// Go作者版权所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package mvs

import (
	"fmt"

	"golang.org/x/mod/module"
)

// Graph实现了MVS算法的增量版本，其中
// 需求由调用方推送，而不是由MVS遍历拉动。
type Graph struct {
	cmp   func(v1, v2 string) int
	roots []module.Version

	required map[module.Version][]module.Version

	isRoot   map[module.Version]bool // 对于根包含true，对于可到达的非根包含false
	selected map[string]string       // 路径→ 版本
}

// NewGraph返回仅包含一组根的增量MVS图
// 依赖项，并对版本字符串使用给定的max函数。
// None
// 调用方必须确保在创建图形时不修改根切片
// 可能正在使用中。
func NewGraph(cmp func(v1, v2 string) int, roots []module.Version) *Graph {
	g := &Graph{
		cmp:      cmp,
		roots:    roots[:len(roots):len(roots)],
		required: make(map[module.Version][]module.Version),
		isRoot:   make(map[module.Version]bool),
		selected: make(map[string]string),
	}

	for _, m := range roots {
		g.isRoot[m] = true
		if g.cmp(g.Selected(m.Path), m.Version) < 0 {
			g.selected[m.Path] = m.Version
		}
	}

	return g
}

// Require添加模块m需要reqs中所有模块的信息。
// reqs切片在传递到Require后不得修改。
// None
// m必须可以通过g的目标的一些现有需求链实现，
// 而且不应该已经被要求了。
// None
// 如果reqs中的任何模块与g的目标具有相同的路径，
// 目标的优先级必须高于req中的版本。
func (g *Graph) Require(m module.Version, reqs []module.Version) {
	// 要帮助捕获断开连接的图形错误，请强制执行所有必需的版本
	// 实际上可以从根访问（因此应该影响
	// 他们命名的模块的选定版本）。
	if _, reachable := g.isRoot[m]; !reachable {
		panic(fmt.Sprintf("%v is not reachable from any root", m))
	}

	// 将reqs截断到其容量，以避免在稍后出现别名错误
	// 从RequiredBy返回并附加到。
	reqs = reqs[:len(reqs):len(reqs)]

	if _, dup := g.required[m]; dup {
		panic(fmt.Sprintf("requirements of %v have already been set", m))
	}
	g.required[m] = reqs

	for _, dep := range reqs {
		// 无论是否选中，都将dep标记为可访问。
		if _, ok := g.isRoot[dep]; !ok {
			g.isRoot[dep] = false
		}

		if g.cmp(g.Selected(dep.Path), dep.Version) < 0 {
			g.selected[dep.Path] = dep.Version
		}
	}
}

// RequiredBy返回传递给Required for m的需求片段（如果有），
// 它的容量缩小到了它的长度。
// 如果没有为m调用Require，RequiredBy（m）返回ok=false。
// None
// 调用者不能修改返回的切片，但可以安全地附加到它
// 并且可能依赖于它不被修改。
func (g *Graph) RequiredBy(m module.Version) (reqs []module.Version, ok bool) {
	reqs, ok = g.required[m]
	return reqs, ok
}

// Selected返回给定模块路径的选定版本。
// None
// 如果未选择任何版本，则所选版本返回“无”。
func (g *Graph) Selected(path string) (version string) {
	v, ok := g.selected[path]
	if !ok {
		return "none"
	}
	return v
}

// BuildList返回图形中所有模块的选定版本，
// 从g根中每个模块路径的选定版本开始。
// None
// 列表中其余元素的顺序是确定的
// 但是武断。
func (g *Graph) BuildList() []module.Version {
	seenRoot := make(map[string]bool, len(g.roots))

	var list []module.Version
	for _, r := range g.roots {
		if seenRoot[r.Path] {
			// 具有相同或不同版本的同一根目录的多个副本，
			// 有点退化：我们将使用及物动词
			// 两者的要求都要考虑，但只有较高的一方可以
			// 可能会被选中。然而，特别是考虑到我们需要
			// 不管怎样，请参阅根映射以了解后面的内容-支持这一点更简单
			// 堕落的情况比禁止更严重。
			continue
		}

		if v := g.Selected(r.Path); v != "none" {
			list = append(list, module.Version{Path: r.Path, Version: v})
		}
		seenRoot[r.Path] = true
	}
	uniqueRoots := list

	for path, version := range g.selected {
		if !seenRoot[path] {
			list = append(list, module.Version{Path: path, Version: version})
		}
	}
	module.Sort(list[len(uniqueRoots):])

	return list
}

// WalkBroadthFirst为每个模块按宽度优先顺序调用f一次
// 图形中显示的“无”以外的版本，无论
// 已选择该版本。
func (g *Graph) WalkBreadthFirst(f func(m module.Version)) {
	var queue []module.Version
	enqueued := make(map[module.Version]bool)
	for _, m := range g.roots {
		if m.Version != "none" {
			queue = append(queue, m)
			enqueued[m] = true
		}
	}

	for len(queue) > 0 {
		m := queue[0]
		queue = queue[1:]

		f(m)

		reqs, _ := g.RequiredBy(m)
		for _, r := range reqs {
			if !enqueued[r] && r.Version != "none" {
				queue = append(queue, r)
				enqueued[r] = true
			}
		}
	}
}

// FindPath报告一个最短的需求路径，该路径从
// 以模块版本m结束的图形，其中f（m）返回true，或
// 如果不存在这样的路径，则为nil。
func (g *Graph) FindPath(f func(module.Version) bool) []module.Version {
	// firstRequires[a]=b表示在
	// 需求图，模块版本a是b首先需要的。
	firstRequires := make(map[module.Version]module.Version)

	queue := g.roots
	for _, m := range g.roots {
		firstRequires[m] = module.Version{}
	}

	for len(queue) > 0 {
		m := queue[0]
		queue = queue[1:]

		if f(m) {
			// 构建反向路径（因为我们从远处开始）
			// 端点），然后将其反转。
			path := []module.Version{m}
			for {
				m = firstRequires[m]
				if m.Path == "" {
					break
				}
				path = append(path, m)
			}

			i, j := 0, len(path)-1
			for i < j {
				path[i], path[j] = path[j], path[i]
				i++
				j--
			}

			return path
		}

		reqs, _ := g.RequiredBy(m)
		for _, r := range reqs {
			if _, seen := firstRequires[r]; !seen {
				queue = append(queue, r)
				firstRequires[r] = m
			}
		}
	}

	return nil
}
